#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;


#if 0
int findLength(vector<int>& nums1, vector<int>& nums2) {
	vector<vector<int>> dp(nums1.size()+1, vector<int>(nums2.size()+1, 0));
	int sum = 0;
	for (int i = 1; i <= nums1.size(); i++)
	{
		for (int j = 1; j <= nums2.size(); j++)
		{
			if (nums1[i - 1] == nums2[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			if (sum<dp[i][j])
			{
				sum = dp[i][j];
			}
		}
	}
	for (int i = 0; i < nums1.size() + 1; i++)
	{
		for (int j = 0; j < nums2.size() + 1; j++)
		{
			cout << dp[i][j] << ' ';
		}
		cout << endl;
	}
	return sum + 1;
}
int main()
{
	vector<int> arr{ 1, 2, 3, 2, 1 };
	vector<int> tmp{ 3, 2, 1, 4, 7 };
	cout << findLength(arr, tmp) << endl;
	return 0;
}

int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
	vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1));
	int sum = 0;
	for (int i = 0; i<nums1.size(); i++)
	{
		for (int j = i + 1; j<nums2.size(); j++)
		{
			if (nums1[i] == nums2[j])
			{
				sum++;
				break;
			}
		}
	}
	return sum;
}
int main()
{
	vector<int> a{ 1, 4, 2 };
	vector<int> b{ 1, 2, 4 };
	cout << maxUncrossedLines(a, b) << endl;
	return 0;
}

int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
	vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
	for (int i = 1; i <= nums1.size(); i++)
	{
		for (int j = 1; j <= nums2.size(); j++)
		{
			if (nums1[i-1] == nums2[j-1])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	return dp[nums1.size()][nums2.size()];
}
int main()
{
	vector<int> a{ 2, 5, 1, 2, 5 };
	vector<int> b{ 10, 5, 2, 1, 5, 2 };
	cout << maxUncrossedLines(a, b) << endl;
	return 0;
}

int maxSubArray(vector<int>& nums) {
	vector<int> dp(nums.size(), 0);
	dp[0] = nums[0];
	for (int i = 1; i<nums.size(); i++)
	{
		if (nums[i] + dp[i - 1]<0)
		{
			dp[i] = nums[i];
		}
		else
		{
			dp[i] = max(nums[i] + dp[i - 1], nums[i]);
		}
	}
	sort(dp.begin(), dp.end());
	return dp[nums.size() - 1];
}
int main()
{
	vector<int> a{ -2, 1, -3, 4, -1, 2, 1, -5, 4 };
	cout << maxSubArray(a) << endl;
	return 0;
}

bool isSubsequence(string s, string t) {
	vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
	for (int i = 1; i <= s.size(); i++)
	{
		for (int j = 1; j <= t.size(); j++)
		{
			if (s[i - 1] == t[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1]+1;
			}
			else
			{
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			}
		}
	}
	return dp[s.size()][t.size()] == s.size() ? true : false;
}
int main()
{
	string s = "abc";
	string t = "ahbgdc";
	cout << isSubsequence(s, t) << endl;
	return 0;
}


int numDistinct(string s, string t) {
	vector<vector<int>> dp(t.size() + 1, vector<int>(s.size() + 1, 0));
	for (int i = 0; i<=t.size(); i++)
	{
		dp[i][0] = 1;
	}
	for (int i = 1; i <= t.size(); i++)
	{
		for (int j = 1; j <= s.size(); j++)
		{
			if (s[j - 1] == t[i - 1])
			{
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	return dp[s.size()][t.size()];
}
int main()
{
	string s = "babgbag";
	string t = "bag";
	cout << numDistinct(s, t) << endl;
	return 0;
}

int minDistance(string word1, string word2) {
	vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
	for (int i = 0; i <= word1.size(); i++)
	{
		dp[i][0] = i;
	}
	for (int i = 0; i <= word2.size(); i++)
	{
		dp[0][i] = i;
	}
	for (int i = 1; i <= word1.size(); i++)
	{
		for (int j = 1; j <= word2.size(); j++)
		{
			if (word1[i - 1] == word2[j - 1])
			{
				dp[i][j] = dp[i - 1][j - 1];
			}
			else
			{
				dp[i][j] = min(dp[i - 1][j - 1]+2, min(dp[i - 1][j]+1, dp[i][j - 1]+1));
			}
		}
	}
	return dp[word1.size()][word2.size()];
}
int main()
{
	string a = "sea";
	string s = "eat";
	cout << minDistance(a, s) << endl;
	return 0;
}

int countSubstrings(string s) {
	vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
	int sum = 0;
	for (int i = s.size()-1; i >= 0; i--)
	{
		for (int j = i; j < s.size(); j++)
		{
			if (s[i] == s[j])
			{
				if (j - i <= 1)
				{
					dp[i][j] = true;
					sum++;
				}
				else if (dp[i + 1][j - 1] == true)
				{
					dp[i][j] = true;
					sum++;
				}
			}
		}
	}
	return sum;
}
int main()
{
	string s = "aaa";
	cout << countSubstrings(s) << endl;
	return 0;
}
#endif

int longestPalindromeSubseq(string s) {
	vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
	int sum = 0;
	for (int i = 0; i<s.size(); i++)
	{
		dp[i][i] = 1;
	}
	for (int i = s.size() - 1; i >= 0; i--)
	{
		for (int j = i; j<s.size(); j++)
		{
			if (i + 1<s.size() && j - 1 >= 0 && i != j&&s[i] == s[j])
			{
				dp[i][j] = dp[i + 1][j - 1] + 2;
			}
			else if (i - 1 >= 0 && j + 1 < s.size() && s[i] != s[j])
			{
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
			}
		}
	}
	return dp[0][s.size() - 1];
}
int main()
{
	string s = "cbbd";
	cout << longestPalindromeSubseq(s) << endl;
	return 0;
}